/*
leetcode 441
你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。
阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

输入：n = 5
输出：2
解释：因为第三行不完整，所以返回 2 。
1+2=3<5
1+2+3=6>5

总结：就是要找出最大的满足 1+2+...+n < target 的个数，也就是n等于多少

公式：求和公式：n*(n+1)/2 <= target

*/
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int arrangeCoins(int n) {
        int left=1,right=n;
        while(left<right){
            //注意这里：要加一
        	int mid=left+(right-left+1)/2;
        	if((long long)mid*(mid+1)<=(long long)2*n){
        		left=mid;
			}else{
				right=mid-1;
			}
		}
		return left;
    }
};

/*
int mid=left+(right-left+1)/2;
原因：
    先加1再除以2是为了让中间值靠右
    left如果不mid+1移动的话，那么就得让mid每次靠右取值。如果left自身有+1移动，就不需要了。
    方案一：(right-left)/2; left=mid+1
    方案二：(right-left+1)/2; left=mid

    因为正常的(left+mid)/2都是向下取整，如果不加上1，left=mid会死循环
    当区间只剩下两个元素的时候，left = mid 和 right = mid - 1 这种划分方式，如果 mid 使用默认下取整的方式，
    在数值上 left = mid，而它对应的其中一个区间是 [mid..right]，在这种情况下，下一轮搜索区间还是 [left..right]，
    搜索区间没有减少，会进入死循环。
*/